#pragma once
#include <iostream>
#include "RBTree.h"
using namespace std;

//template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
//class map
//{
//public:
//	typedef Key key_type;
//	typedef T data_type;
//	typedef T mapped_type;
//	typedef pair<const Key, T> value_type;
//
//private:
//	typedef rb_tree<key_type, value_type,
//		select1st<value_type>, key_compare, Alloc> rep_type;
//	rep_type t;
//};

namespace xy
{
	template <class T,class V>
	class map
	{
	public:
		struct MapKeyOfT
		{
			const T& operator()(const pair<T, V>& kv)
			{
				return kv.first;
			}
		};

		//typedef typename RBTreeIterator<V, pair<T,V>&, pair<T,V>*> iterator;
		//typedef typename RBTreeIterator<V, const pair<T,V>&, const pair<T,V>*> const_iterator;
		typedef typename RBTree<T, pair<const T, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<T, pair<const T, V>, MapKeyOfT>::Const_iterator const_iterator;
		
		pair<iterator, bool> insert(const pair<T,V>& data)
		{
			return _t.Insert(data);
		}

		const_iterator begin() const
		{
			return _t.Begin();
		}

		const_iterator end() const
		{
			return _t.End();
		}

		iterator begin()
		{
			return _t.Begin();
		}

		iterator end()
		{
			return _t.End();
		}

		V& operator[](const T& key)
		{
			pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
			return ret.first->second;
		}

	private:
		RBTree<T, pair<const T,V>, MapKeyOfT> _t;

	};

	void TestMymap1()
	{
		map<int, int> m1;
		m1.insert({ 2,2 });
		m1.insert({ 1,1 });
		m1.insert({ 3,3 });
		m1.insert({ 4,4 });
		m1.insert({ 5,5 });

		map<int,int>::iterator it = m1.begin();
		while (it != m1.end())
		{
			cout << it->first << " ";
			++it;
		}
		cout << endl;
		const map<int, int> m2 = m1;
		map<int, int>::const_iterator it2 = m2.begin();
		while (it2 != m2.end())
		{
			cout << it2->first << " ";
			++it2;
		}
		cout << endl;

	}

	void TestMymap2()
	{
		map<string, int> m1;
		string arr[] = {"haha", "haha", "haha", "haha", "haha", "haha", "xxxx", "xxxx", "xxxx", "xxxx", "xxxx",
			"Love", "Love", "Love", "Love", "Love", };
		for (auto& e : arr)
		{
			m1[e]++;
		}
		for (auto& kv : m1)
		{
			cout << kv.first << ":" << kv.second << endl;
		}
	}

}